/**
 * https://leetcode-cn.com/problems/balanced-binary-tree/
 * 判断一颗二叉树搜索树是不是平衡二叉树
 * @param root 
 */
const isBalanced = (root: TreeNode | null): boolean => {
    // 树为空, 是一颗平衡二叉树
    if (root === null) return true;

    let isBal = true

    /**
     * 求树的高
     * @param n 
     */
    const height = (n: TreeNode | null): number => {
        if (n === null || !isBal) return 0

        // 1. 求左子树高
        const l = height(n.left);

        // 2. 求右子树高
        const r = height(n.right);

        // 判断左右子树高度差
        if (Math.abs(l - r) > 1) isBal = false;

        return Math.max(l, r) + 1
    }

    height(root);

    return isBal
};